class Node:  # 二叉树的节点
    def __init__(self, data=None, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:#二叉树
    def __init__(self):
        self.root = None

    def build_tree(self):  # 层次建树
        a = [i for i in range(1, 10)]
        b = []
        for i in a:
            node = Node(i)
            if self.root == None:
                self.root = node
                b.append(node)
                continue
            if b[0].lchild == None:
                b[0].lchild = node
            else:
                b[0].rchild = node
                del (b[0])
            b.append(node)

    def pre_order(self, node):  # 前序遍历
        if node:
            print(node.data, end=" ")
            self.pre_order(node.lchild)
            self.pre_order(node.rchild)
        else:
            return

    def in_order(self, node):  # 中序遍历
        if node:
            self.in_order(node.lchild)
            print(node.data, end=" ")
            self.in_order(node.rchild)
        else:
            return

    def post_order(self, node):  # 后序遍历
        if node:
            self.post_order(node.lchild)
            self.post_order(node.rchild)
            print(node.data, end=" ")
        else:
            return

    def level_order(self, node):  # 层序遍历
        a_list = []
        a_list.append(node)
        while a_list:
            a = a_list.pop(0)
            print(a.data, end=" ")
            if a.lchild and a.rchild:
                a_list.append(a.lchild)
                a_list.append(a.rchild)
            elif a.lchild:
                a_list.append(a.lchild)


if __name__ == '__main__':
    tree1 = BinaryTree()
    tree1.build_tree()
    tree1.pre_order(tree1.root)
    print()
    tree1.in_order(tree1.root)
    print()
    tree1.post_order(tree1.root)
    print()
    tree1.level_order(tree1.root)
    print()
